Éléments d'analyse des algorithmes

Table des matières

1. Analyse d'algorithmes
2. Algorithmes divers
3. Éléments de complexité
Appendice : Effets de bords

1. Analyse d'algorithmes

1.1. Un premier exemple

La fonction suivante prend en argument deux entiers positifs $n,b$, avec $b\gt 0$. Que renvoie-t-elle ?

def mystere(n, b):
    m = n
    while m >= b:
        m = m - b
    return m

1.1.1. Terminaison de l'algorithme

Quand un algorithme utilise une boucle while, il faut vérifier que celle-ci termine, c'est-à-dire que la condition d'arrêt finit (ici m < b) par être vérifiée.

Pour cela, on utilise un variant de boucle. Dans la majorité des cas, c'est une variable prenant des valeurs entières positives dont la valeur décroît strictement à chaque itération de la boucle. Comme il n'existe pas de suite d'entiers naturels strictement décroissante, cela justifie que la boucle ne tourne qu'un nombre fini de fois, donc que la condition d'arrêt est atteinte.

Dans la fonction mystere, la variable m prend des valeurs entières positives (car la boucle s'arrête si $m\lt 0$) et strictement décroissantes (car $b\gt 0$). Cela justifie la terminaison de l'algorithme. On a également identifié l'hypothèse importante ($b\gt 0$).

1.1.2. Correction de l'algorithme

La fonction mystere détermine le reste de la division euclidienne de n par b.

Pour justifier qu'elle fait bien cela, on utilise un invariant de boucle. On identifie une quantité qui ne change pas de valeur, ou une assertion mathématique qui reste vraie à chaque itération de la boucle.

Un premier invariant
Dans la fonction mystere, on a toujours $$m \equiv n [b].$$ Formellement, cela se démontre par récurrence.
- C'est vrai au début de la boucle, car $m$ a pour valeur initiale $n$.
- Si c'est vrai à la fin d'une itération de la boucle, en notant $m^+$ la nouvelle valeur de $m$ dans l'itération d'après, on a $m^+ = m - b$, donc $m^+ \equiv m- b \equiv m \equiv n [b]$, d'après l'hypothèse de récurrence.
Un second invariant

On peut énoncer un invariant plus précis, sous la forme d'une propriété qui dépend du nombre d'itération de la boucle : $$\text{Après la i-ème itération de la boucle, } m = n - ib$$

Cet invariant se justifie également par récurrence.
Preuve de la correction
On peut maintenant justifier la correction de l'algorithme.
1. Une fois la boucle terminée, d'après la condition d'arrêt, on a $m\lt b$.
2. Si on note $m^{-}$ la valeur précédente de la variable m, on a $m = m^{-} - b$, et comme $m^{-}\geq b$, on a $m\geq 0$.
3. D'après le premier invariant de boucle, on a $m\equiv n [b]$
Ces trois points impliquent que la valeur finale de $m$, renvoyée par la fonction, est bien le reste de la division euclidienne de $n$ par $b$.

1.1.3. Complexité de l'algorithme

On appelle complexité d'un algorithme le nombre d'opérations exécutées en fonction de la taille des paramètres d'entrée.

Comme le quotient de la division euclidienne de $n$ par $b$ est $\lfloor \frac{n}{b}\rfloor$, d'après le second invariant de boucle, la boucle de la fonction mystere sera exécutée $\lfloor \frac{n}{b}\rfloor$ fois.

À l'intérieur de la boucle, on exécute une soustraction et une affectation. La fonction réalise donc au total $\lfloor \frac{n}{b}\rfloor$ soustractions et affectations et $\lfloor \frac{n}{b}\rfloor + 1$ comparaisons.

On dira que la complexité est en $O(\frac{n}{b})$, ou, si l'on ne considère que $n$ comme paramètre, en $O(n)$.

1.2. Deuxième exemple : recherche du minimum d'une liste

La fonction ci-contre renvoie le minimum d'une liste non vide. Décrire un invariant de boucle.

def min_liste(l):
    m, n = l[0], len(l)
    for i in range(1,n):
        if l[i] < m:
            m = l[i]
    return m

On note $n$ la longueur de la liste.

Terminaison: Il n'y a rien à justifier, une boucle for termine toujours.
Invariant de boucle: Pour tout $i\in\db{0,n - 1}$, après la $i$−ième boucle, $m$ est le minimum des $i+1$ premiers éléments de la liste. En notant $m_i$ la valeur de $m$ à l'issue de la boucle sur $i$, on a $m_i = \min \texttt{l}[:i+1]$.
Correction: Découle de l'invariant : à la fin de la boucle, on aura $m = \min \texttt{l}[:n] = \min \texttt{l}$.
Complexité: On réalise $n-1$ comparaisons, et au plus $n$ affectations. La complexité est donc linéaire en la taille de la liste, ou en $O(n)$.

1.3. Autres exemples

1.3.1. Première fonction

La fonction mystere suivante prend en argument
un entier naturel $n\geq 1$.

def mystere(n):
    m = 1
    i = 0
    while 2 * m <= n:
        i = i + 1
        m = 2 * m
    return i

Justifier brièvement la terminaison.
Donner un invariant de boucle.
Que renvoie cette fonction ? On donnera une expression algébrique simple.
Quelle est la complexité de l'algorithme ?

1.3.2. Deuxième fonction

def mystere(n):
    l = []
    s = n
    while s != 0:
        r = s % 2
        l.append(r)
        s = (s - r) // 2
        # s = s // 2 est équivalent
    return l

Que renvoie cette fonction ?
Justifier la terminaison.
Donner un invariant de boucle. Ici, on expliquera simplement que représentent l et s à l'issue de la $i$−ième boucle.
Quelle est la complexité de l'algorithme ?

1.3.3. Fonction mystère

def myst(l):
    i, j = 0, len(l)-1
    while i <= j:
        if l[i] == l[j]:
            i += 1
            j -= 1
        else:
            return False
    return True

Que fait cette fonction ?
Expliciter un invariant de boucle.
Justifier la terminaison.
Justifier la correction.

2. Algorithmes divers

2.1. Algorithme d'Euclide

def pgcd(a, b):
    a, b = max(a,b), min(a,b)
    while b > 0:
        a, b = b, a % b
    return a

Justifier la terminaison puis la correction de l'algorithme en explicitant un invariant de boucle.
On considère la suite de Fibonacci définie par $F_1 = 1$, $F_2 = 1$ et $\forall n\in\N^*, F_{n+2} = F_{n+1} + F_n$. Montrer par récurrence d'ordre $2$ que si $a\leq F_n$ et $b\leq F_n$ alors l'algorithme d'Euclide termine en au plus $n$ étapes.
En déduire que la complexité de l'algorithme d'Euclide est logarithmique en $\min(a,b)$.

2.2. Un algorithme dichotomique

def dicho(l, e):
    a, b = 0, len(l)-1
    if e < l[a] or l[b] <= e:
        return False
    while b-a > 1:
        c = a + (b-a) // 2
        if l[c] <= e:
            a = c
        else:
            b = c
    return (e == l[a] or e == l[b])

La fonction ci-contre prend en argument une liste l triée et un élément e.

Que fait cette fonction ?
Expliciter un invariant de boucle.
En explicitant un variant de boucle, justifier la terminaison.
Justifier la correction.

Écrire une version de cet algorithme utilisant une fonction auxiliaire récursive prenant en argument la liste l et deux indices a, b dans l.

2.3. Tri par bulles

def tri_bulles(l):
    n, trié = len(l), False
    while (not trié):
        trié = True
        for j in range(n-1):
            if l[j] > l[j+1]:
                trié = False
                l[j], l[j+1] = l[j+1], l[j]

Justifier que si l'algorithme précédent termine, il est correct. Cette propriété s'appelle la correction partielle de l'algorithme.
On propose deux méthodes différentes pour justifier la terminaison.
1. Identifier un invariant de la boucle while.
  
  En déduire que l'algorithme précédent termine et que sa complexité est au pire des cas quadratique.
2. Si $\l = (\l_1,\dots,\l_n)$ est une liste de taille $n$, on note $I_\l = \big|\{(i,j),\, i\lt j\et \l_i \gt \l_j \}\big|$ le nombre d'inversions de $\l$. Soit $k\lt n$ tel que $\l_k \gt \l_{k+1}$. On note $\l'$ la liste obtenue après échange des éléments $k$ et $k+1$. Montrer que $I_{\l'} \lt I_{\l}$.
  
  En déduire que l'algorithme précédent termine. Donner une majoration de sa complexité dans le pire des cas.

2.4. Sur un graphe

On considère un graphe orienté pondéré à $n$ sommets, dont les poids peuvent être négatifs, et un sommet initial $s_0$. L’algorithme de Bellman-Ford fonctionne comme suit, en utilisant un tableau B.

pour chaque sommet $a$
- initialiser $\texttt{B[a]} = +\i$
initialiser $\texttt{B}[s_0] = 0$
répéter $n-1$ fois :
- pour chaque arête $u\ra v$,
  
  $B[u] \leftarrow \min(B[u], p(u, v) + B[v])$

Quelle est la complexité de l'algorithme ?
Pour $i\in\db{1, n-1}$, à l'issue de la $i$-ème itération de la boucle extérieure, que représente $B(u)$ ?
Quel est l'avantage de cet algorithme, par rapport à celui de Dijkstra ?
Comment modifier l'algorithme pour détecter l'existence d'un cycle de poids total négatif ?

3. Éléments de complexité

3.1. Complexité et temps d'exécution

Sous l'hypothèse d'un milliard d'opérations élémentaires par seconde, le tableau suivant indique un ordre de grandeur du temps d'exécution d'un algorithme en fonction de sa complexité et du paramètre $n$.

Complexité	Notation	$n=10^3$	$n = 10^5$	$n = 10^7$
logarithmique	$O(\ln n)$	$10 \, ns$	$15 \, ns$	$20 \, ns$
linéaire	$O(n)$	$1 \,\mu s$	$100 \,\mu s$	$10 \,ms$
quasi-linéaire	$O(n \ln n)$	$10 \,\mu s$	$1 \, ms$	$200 \,ms$
quadratique	$O(n^2)$	$1 \,ms$	$10 \, s$	$30\, h$
cubique	$O(n^3)$	$1 \,s$	$10 \, j$	$\i$
exponentielle	$2^{O(n)}$	$\i$	$\i$	$\i$

La notation $O$ est une complexité asymptotique, et elle cache une constante multiplicative. Pour des problèmes compliqués, un algorithme peut avoir une meilleure complexité asymptotique théorique mais être moins performant en pratique.

On utilise parfois la notation $f(n) = \Theta(g(n))$, pour signifier qu'il existe deux constantes $C_1$ et $C_2$ telles que $C_1 g(n)\leq f(n)\leq C_2 g(n)$, pour $n$ assez grand.

3.2. Quelques fonctions élémentaires

Sur une liste

def myst(l):
    n = len(l)
    for i in range(n-1):
        if l[i] in l[i+1:]:
            return False
    return True

Que fait cette fonction ?
Quelle est sa complexité dans le pire des cas, en terme de la longueur $n$ de la liste.
Proposer une variante avec une meilleure complexité asymptotique.

Avec une fonction auxiliaire

def myst_aux(l):
    n = len(l)
    s = 0
    for a in l:
        s += a
    return s / n

def myst(l):
    n = len(l)
    s = 0
    for a in l:
        s += (a - myst_aux(l)) ** 2
    return s / n

Que renvoient les fonctions myst_aux, myst ?
Quelle est la complexité de myst ? Comment faire mieux ?

Un algorithme pas exactement quadratique

def myst(n):
    tab = [True] * (n+1)
    l = []
    tab[0], tab[1] = False, False
    for i in range(2, n+1):
        if tab[i]:
            l.append(i)
            j = 2*i
            while j <= n:
                tab[j] = False
                j += i
    return l

Décrire ce que renvoie la fonction myst.
Exprimer la complexité de cette fonction à l'aide d'une somme.

On a $\sum\limits_{k=1}^n \frac{1}{k} \sim \ln n$ et $\sum\limits_{\substack{p=1 \\ p \text{ premier}}}^n \frac{1}{p} \sim \ln (\ln n)$.

3.3. Coupe maximale d'un tableau

Étant donné une liste $\texttt{l} = [a_0, …, a_{n-1}]$ de nombres réels, on appelle coupe de $\texttt{l}$ toute somme de termes consécutifs de $\texttt{l}$, c'est-à-dire toute somme de la forme $s = \sum\limits_{k = i}^{j} a_k$, pour $0\leq i\leq j\leq n-1$. Le but est de déterminer une coupe maximale de $\texttt{l}$.

Implémentation naïve.
1. Écrire une fonction coupe qui prend en argument la liste l, et deux indices $i, j$ et renvoie la valeur $\sum_{k = i}^{j} a_k$.
2. Écrire une fonction coupe_max_naive qui prend en argument la liste l et renvoie la valeur d'une coupe maximale de l.
  
  On calculera toutes les coupes possibles.
3. Quelle est la complexité de cette implémentation ?
Implémentation quadratique.
1. Écrire une fonction coupe_max_depuis qui prend en argument la liste l et un indice $i$ et renvoie la coupe maximale de l, parmi les coupes commençant à l'indice i donné, c'est-à-dire parmi les coupes de la forme $\sum_{k=i}^j a_k$, pour $j\in\db{i, n-1}$.
  
  On veut une complexité en $O(n)$. On n'utilisera pas la fonction coupe.
2. En déduire une fonction coupe_max_quad qui renvoie la valeur d'une coupe maximale, avec une complexité quadratique.
Écrire une fonction coupe_max_lin avec une complexité linéaire.

Appendice : Effets de bords

On dit qu'une fonction a des effets de bords si elle modifie l'environnement global, en pratique en modifiant un de ses arguments qui a un type mutable.

def tri_mutable(l):
    l.sort()

def tri_pur(l):
    return sorted(l)

On peut transformer une fonction avec des effets de bords en une fonction pure, et réciproquement, avec des copies.

def tri_mut_avec_pur(l):
    ll = tri_pur(l)
    for i in range(len(l)):
        l[i] = ll[i]

def tri_pur_avec_mut(l):
    ll = l.copy()
    tri_mutable(ll)
    return ll